package 力扣日常刷题.木23一月.第03天303;

import 力扣日常刷题.ListNode;

/**
 * @author 帅小伙
 * @date 2022/3/3
 * @description
 */
public class Demo29链表排序 {

    public ListNode sortList(ListNode head) {
        if(head == null || head.next == null) return head;
        // 第一步：将链表拆成两半
        ListNode fast = head, slow = head, prev = head;
        while(fast != null && fast.next != null) {
            prev = slow;
            slow = slow.next;
            fast = fast.next.next;
        }
        prev.next = null;
        // 第二步：将两部分的链表分别排序
        ListNode l1 = sortList(head);
        ListNode l2 = sortList(slow);
        // 第三步：合并两个有序链表
        return merge(l1,l2);
    }

    private ListNode merge(ListNode l1, ListNode l2) {
        ListNode p = new ListNode(), l = p;
        while(l1 != null && l2 != null) {
            if(l1.val < l2.val) {
                p.next = l1;
                l1 = l1.next;
            } else {
                p.next = l2;
                l2 = l2.next;
            }
            p = p.next;
        }
        p.next = l1 ==null ? l2 : l1;
        return l.next;
    }


}
